package 二分.二分答案;

import java.util.Arrays;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/2/5 16:52
 */
public class leetcode礼盒的最大甜蜜度 {
    /*
        二分答案的 难点，
        可能二分答案的 范围，可以看出来
        难点在于，怎么去 根据答案 去找到满足 答案的 条件
        （单调性！）
        给出条件，找到满足条件的 最好的值
        枚举答案，怎么 去反过来去 满足 条件
     */


    public int solution(int price[], int k) {
        Arrays.sort(price);
        int l = 0, r = 1000_000_000;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (check(mid, price) < k) {
                r = mid - 1;
            } else {
                l = mid;
            }

        }
        return l;
    }

    /*
    这个题的 check 方法，确实挺难 想的！
     */
    private int check(int mid, int[] price) {
        int ans = 1, last = price[0];
        for (int i = 1; i < price.length; i++) {
            if (price[i] - last >= mid) {
                ans++;
                last = price[i];
            }
        }
        return ans;
    }

    private int checkError(int mid, int[] price) {
        int ans = 0;
        for (int i = 1; i < price.length; i++) {
            if (price[i] - price[i - 1] >= mid) {
                ans++;
            }
        }
        return ans;
    }
    /*
    用动态规划，怎么写
    给定一个 集合 price， 从中挑选 k 元素， 问怎么挑， 才能使 礼品的 甜蜜 度最大
    1. 从集合中选出 k 个元素，放在哪里面呢？
    2. 放在一个集合里面的话，在递归当中确实有些难做！
     */

    /*
     给出一个 集合 nums， 求出 nums中， 求出 任意两个元素间差值的 绝对值的最小值
     A: 直接排序，找相邻元素的 差值，找出最小的即可
     */
    public int findDistacne(int nums[]) {
        Arrays.sort(nums);
        int min = Integer.MAX_VALUE;
        for (int i = 1; i < nums.length; i++) {
            min = Math.min(min, nums[i] - nums[i - 1]);
        }
        return min;
    }

}
